public class Main {
    public static void main(String[] args) {
        System.out.println(new Solution().countSubstringsManacher("abc"));
        System.out.println(new Solution().countSubstringsManacher("aaa"));
    }
}

class Solution {
    //从每一个可能的回文中心向两端扩展
    public int countSubstrings(String s) {
        int ans = 0;

        for (int i = 0; i < s.length(); i++) {
            ans++;
            //奇数
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                ans++;
                l--;
                r++;
            }
            //偶数
            l = i;
            r = i + 1;
            while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
                ans++;
                l--;
                r++;
            }
        }
        return ans;
    }

    //Manacher
    public int countSubstringsManacher(String s) {
        StringBuffer sb = new StringBuffer("$#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i));
            sb.append("#");
        }
        sb.append("%");

        int[] f = new int[sb.length()];
        int cMax = 0, rMax = 0;
        int ans = 0;
        for (int i = 1; i < f.length - 1; i++) {
            f[i] = 1;
            if (i <= rMax) {
                int j = 2 * cMax - i;
                f[i] = Math.min(rMax - i + 1, f[j]);
            }
            while (sb.charAt(i - f[i]) == sb.charAt(i + f[i])) {
                f[i]++;
            }

            if (i + f[i] - 1 > rMax) {
                rMax = i + f[i] - 1;
                cMax = i;
            }

            ans += f[i] / 2;
        }
        return ans;
    }

    //申请dp数组的动态规划方法
    public int countSubstrings1(String s) {
        int ans = 0;
        boolean[][] dp = new boolean[s.length()][s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            dp[i][0] = true;
            dp[i][1] = true;
        }
        ans = s.length();

        for (int w = 2; w <= s.length(); w++) {
            for (int i = 0; i + w <= s.length(); i++) {
                dp[i][w] = dp[i + 1][w - 2] && s.charAt(i) == s.charAt(i + w - 1);
                if (dp[i][w]) {
                    ans++;
                }
            }
        }
        return ans;
    }
}